/*
 * Project: Sudoku Explainer
 * Copyright (C) 2006-2007 Nicolas Juillerat
 * 
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.data;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Vector;

/**
 * A Sudoku grid.
 * <p>
 * Contains the 9x9 array of cells, as well as methods
 * to manipulate regions (rows, columns and blocks).
 * <p>
 * Horizontal coordinates (for Cells) range from 0 (leftmost) to
 * 8 (rightmost). Vertical coordinates range from 0 (topmost) to
 * 8 (bottommost).
 */
public class Grid implements Serializable, Puzzle {

	private static final long serialVersionUID = 7126641188993458274L;

	// standard block codes (3*3 squares)
	private static final byte[][] sBlockCodes = new byte[][] {
		{0, 0, 0, 3, 3, 3, 6, 6, 6},
		{0, 0, 0, 3, 3, 3, 6, 6, 6},
		{0, 0, 0, 3, 3, 3, 6, 6, 6},
		{1, 1, 1, 4, 4, 4, 7, 7, 7},
		{1, 1, 1, 4, 4, 4, 7, 7, 7},
		{1, 1, 1, 4, 4, 4, 7, 7, 7},
		{2, 2, 2, 5, 5, 5, 8, 8, 8},
		{2, 2, 2, 5, 5, 5, 8, 8, 8},
		{2, 2, 2, 5, 5, 5, 8, 8, 8},
	   };
	
	/*
     * Cells of the grid. First array index is the vertical index (from top
     * to bottom), and second index is horizontal index (from left to right).
     */
    private final Cell[][] cells = new Cell[9][9];

    // Views
    private final Row[] rows = new Row[9];
    private final Column[] columns = new Column[9];
    private final Block[] blocks = new Block[9];
    private boolean isJigsaw;
    private byte[][] mBlockCodes = null;
    private ExtraRegionType type;
    private List<ExtraRegionExtended> extraRegions = null;
    
    transient private List<Class<? extends Region>> _allRegionTypes = null;

    private double difficulty;

    /**
     * Create a new 9x9 Sudoku grid.
     * All cells are set to empty.
     */
    public Grid(Grid grid) {
    	this(grid.type, grid.isJigsaw, grid.mBlockCodes);
    }
    
    /**
     * Create a new 9x9 Sudoku grid.
     * All cells are set to empty.
     */
    public Grid(ExtraRegionType type, boolean isJigsaw, byte[][] blockCodes) {
    	this.type = type;
    	this.isJigsaw = isJigsaw;
    	this.mBlockCodes = (blockCodes==null) ? sBlockCodes : blockCodes;

    	// create 81 cells
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                cells[y][x] = new Cell(this, x, y);
            }
        }
        
        // Build subparts views
        for (int i = 0; i < 9; i++) {
            rows[i] = new Row(this, i);
            columns[i] = new Column(this, i);
            blocks[i] = new Block(this, i, mBlockCodes);
        }
        extraRegions = ExtraRegionManager.getExtraRegionsExtended(type, this);
    }

    @Override
    public boolean isJigsaw() {
    	return isJigsaw;
    }
    
    @Override
    public byte[][] getBlockCodes() {
    	return mBlockCodes;
    }
    
    @Override
    public boolean hasExtraRegions() {
    	return (type!=ExtraRegionType.NONE);
    }
    
    @Override
    public ExtraRegionType getExtraRegionType() {
    	return type;
    }
    
    /**
     * Get the cell at the given coordinates
     * @param x the x coordinate (0=leftmost, 8=rightmost)
     * @param y the y coordinate (0=topmost, 8=bottommost)
     * @return the cell at the given coordinates
     */
    public Cell getCell(int x, int y) {
        return cells[y][x];
    }

    public Cell getCell(int pos) {
        return cells[pos/9][pos%9];
    }

    /**
     * Get the 9 regions of the given type
     * @param regionType the type of the regions to return. Must be one of
     * {@link Block}, {@link Row} or {@link Column}.
     * @return the 9 regions of the given type
     */
    public Region[] getRegions(Class<? extends Region> regionType) {
        return (regionType==Row.class) ? rows :
        	   (regionType == Column.class) ? columns :
        	   (regionType == Block.class) ? blocks :
        	   extraRegions.toArray(new ExtraRegionExtended[0]);	// has to be [0] because we just want an empty array not one with a null element
    }

    // Cell values

    /**
     * Set the value of a cell
     * @param x the horizontal coordinate of the cell
     * @param y the vertical coordinate of the cell
     * @param value the value to set the cell to. Use 0 to clear the cell.
     */
    public void setCellValue(int x, int y, int value, boolean isGiven) {
        cells[y][x].setValue(value, isGiven);
    }

    /**
     * Get the value of a cell
     * @param x the horizontal coordinate of the cell
     * @param y the vertical coordinate of the cell
     * @return the value of the cell, or 0 if the cell is empty
     */
    public int getCellValue(int x, int y) {
        return cells[y][x].getValue();
    }

    /**
     * Get the row at the given location
     * @param x the horizontal coordinate
     * @param y the vertical coordinate
     * @return the row at the given coordinates
     */
    private Row getRowAt(int x, int y) {
        return rows[y];
    }

    /**
     * Get the column at the given location
     * @param x the horizontal coordinate
     * @param y the vertical coordinate
     * @return the column at the given location
     */
    private Column getColumnAt(int x, int y) {
        return columns[x];
    }

    /**
     * Get the 3x3 block at the given location
     * @param x the horizontal coordinate
     * @param y the vertical coordinate
     * @return the block at the given coordinates (the coordinates
     * are coordinates of a cell)
     */
    private Block getBlockAt(int x, int y) {
    	CellPosition pos = new CellPosition(x, y);
    	for (Block block:blocks) {
    		if (block.contains(pos)) return block;
    	}
    	return null;	// should never happen
    }

    /**
     * Get the extra region at the given location
     * @param x the horizontal coordinate
     * @param y the vertical coordinate
     * @return the extra regions at the given coordinates, the array is never null but may contain zero elements
     * --> for(Region region:getExtraRegionAt(x, y) works but no direct access like region[0]
     */
    private ExtraRegionExtended[] getExtraRegionAt(int x, int y) {
    	List<ExtraRegionExtended> result = new Vector<ExtraRegionExtended>(); 
    	if (hasExtraRegions()) {
        	for(ExtraRegionExtended region:extraRegions) {
        		for (Cell cell:region.getCellSet()) {
        			if (cell.getX()==x && cell.getY()==y) {
        				result.add(region);
        				break;
        			}
        		}
        	}
    	}
        return result.toArray(new ExtraRegionExtended[result.size()]);
    }

    public ArrayList<Region> getRegionsAt(Cell cell) {
		ArrayList<Region> regions = new ArrayList<Region>();
		for (Class<? extends Region> regionType : getRegionTypes()) {
			for (Region region:getRegionsAt(regionType, cell)) {
				regions.add(region);
			}
		}
		return regions;
    }
    
    public Region[] getRegionsAt(Class<? extends Region> regionType, Cell cell) {
        return getRegionsAt(regionType, cell.getX(), cell.getY());
    }

    private Region[] getRegionsAt(Class<? extends Region> regionType, int x, int y) {
    	return (regionType.equals(Row.class)) ? new Region[] {getRowAt(x, y)} :
    		   (regionType.equals(Column.class)) ? new Region[] {getColumnAt(x, y)} :
      		   (regionType.equals(Block.class)) ? new Region[] {getBlockAt(x, y)} :
       		   (regionType.equals(ExtraRegionExtended.class)) ? getExtraRegionAt(x, y) : null;
    }

    /**
     * Works for Blocks, Rows and Columns perfectly.
     * For Extra Regions it will return the first found extra region --> doesn't work for X-Sudoku! 
     */
    public Region getRegionAt(Class<? extends Region> regionType, Cell cell) {
        return getRegionAt(regionType, cell.getX(), cell.getY());
    }

    /**
     * Works for Blocks, Rows and Columns perfectly.
     * For Extra Regions it will return the first found extra region --> doesn't work for X-Sudoku! 
     */
    public Region getRegionAt(Class<? extends Region> regionType, int x, int y) {
    	if (regionType.equals(ExtraRegionExtended.class)) {
    		ExtraRegionExtended[] tmp = getExtraRegionAt(x, y);
    		return (tmp==null || tmp.length==0) ? null : tmp[0];
    	}
    	return (regionType.equals(Row.class)) ? getRowAt(x, y) :
 		   	   (regionType.equals(Column.class)) ? getColumnAt(x, y) :
   		       (regionType.equals(Block.class)) ? getBlockAt(x, y) : null;
    }

    /**
     * Get a list containing the four classes corresponding to the
     * three region types (row, column, block, extraregion)
     * @return a list of the three region types. The resulting list can not be modified
     */
    public List<Class<? extends Region>> getRegionTypes() {
        if (_allRegionTypes == null) {
        	_allRegionTypes = new ArrayList<Class<? extends Region>>(3);
            if (this.hasExtraRegions()) _allRegionTypes.add(ExtraRegionExtended.class);
        	_allRegionTypes.add(Block.class);
        	_allRegionTypes.add(Row.class);
        	_allRegionTypes.add(Column.class);
            _allRegionTypes = Collections.unmodifiableList(_allRegionTypes);
        }
        return _allRegionTypes;
    }

    /**
     * Rebuild, for each empty cell, the set of potential values.
     */
    public void rebuildPotentialValues() {
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                Cell cell = getCell(x, y);
                if (cell.getValue() == 0) {
                    for (int value=1; value<=9; value++) {
                        cell.addPotentialValue(value);
                    }
                }
            }
        }
        cancelPotentialValues();
    }

    /**
     * Remove all illegal potential values according
     * to the current values of the cells.
     * Can be invoked after a new cell gets a value.
     */
    public void cancelPotentialValues() {
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                Cell cell = getCell(x, y);
                if (cell.getValue() != 0) {
                    cell.clearPotentialValues();
                }
            }
        }
        cancelBy(Block.class);
        cancelBy(Row.class);
        cancelBy(Column.class);
        if (hasExtraRegions()) cancelBy(ExtraRegionExtended.class);
    }

    /**
     * This is the basic Sudoku rule: If a cell contains a value,
     * that value can be removed from the potential values of
     * all cells in the same block, row or column.
     * @param partType the Class of the part to cancel in
     * (block, row or column)
     */
    private <T extends Region> void cancelBy(Class<T> partType) {
        Region[] parts = getRegions(partType);
        for (Region part : parts) {
            for (int i = 0; i < 9; i++) {
                Cell cell = part.getCell(i);
                if (!cell.isEmpty()) {
                    int value = cell.getValue();
                    // Remove the cell value from the potential values of other cells
                    for (int j = 0; j < 9; j++) part.getCell(j).removePotentialValue(value);
                }
            }
        }
    }

	/**
     * Creates and returns a copy of the Cell.
     */
    public Grid clone() {
    	Grid grid = new Grid(this);
    	copyTo(grid);
    	return grid;
    }

    /**
     * Copy the content of this grid to another grid.
     * The values of the cells and their potential values are copied.
     * @param other the grid to copy this grid to
     */
    public void copyTo(Grid other) {
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                this.cells[y][x].copyTo(other.cells[y][x]);
            }
        }
    }

    /**
     * Get the number of occurances of a given value in this grid
     * @param value the value
     * @return the number of occurances of a given value in this grid
     */
    public int getCountOccurancesOfValue(int value) {
        int result = 0;
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                if (cells[y][x].getValue() == value)
                    result++;
            }
        }
        return result;
    }

    /**
     * Get a string representation of this grid.
     * For debugging purpose only.
     */
    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                int value = getCellValue(x, y);
            	result.append((value == 0) ? "0" : value); //$NON-NLS-1$
            }
            result.append('\n');
        }
/*        if (isJigsaw()) {
            result.append('|');
            for (int y = 0; y < 9; y++) {
                for (int x = 0; x < 9; x++) {
                    int value = this.mBlockCodes[x][y];
                	result.append((value == 0) ? "0" : value);
                }
                //result.append('\n');
            }
        }*/
        return result.toString();
    }

    /**
     * String representation of the grid.
     * For debugging purposes only.
     */
    public String toFullString() {
        StringBuilder result = new StringBuilder();
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
            	Cell cell = getCell(x, y);
            	result.append((cell.isEmpty()) ? "." : cell.getValue()); //$NON-NLS-1$
                result.append('(');
            	for (int i=1;i<=9;i++) {
            		result.append(cell.hasPotentialValue(i) ? i : "-"); //$NON-NLS-1$
            	}
                result.append(')');
            }
            result.append('\n');
        }
        return result.toString();
    }

    /**
     * Compare two grids for equality. Comparison is based on the values
     * of the cells and on the potential values of the empty cells.
     */
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Grid)) return false;
        Grid other = (Grid)o;
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                Cell thisCell = this.getCell(x, y);
                Cell otherCell = other.getCell(x, y);
                if (thisCell.getValue() != otherCell.getValue()) return false;
                if (!thisCell.getPotentialValues().equals(otherCell.getPotentialValues())) return false;
            }
        }
        return true;
    }

    @Override
    public int hashCode() {
        int result = 0;
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                Cell cell = getCell(x, y);
                result ^= cell.getValue();
                result ^= cell.getPotentialValues().hashCode();
            }
        }
        return result;
    }

	public Collection<Cell> findDigits(int value) {
		ArrayList<Cell> cells = new ArrayList<Cell>();
		if (value>0) {
	    	for (int y=0; y<9; y++) {
	        	for (int x=0; x<9; x++) {
	        		Cell cell = getCell(x, y);
	        		if (cell.getValue()==value) cells.add(cell);
	        	}
	    	}
		}
    	cells.trimToSize();
    	return cells;
	}
	
	public Map<Cell, BitSet> findPotentials(Integer... args) {
		HashMap<Cell, BitSet> potentials = new HashMap<Cell, BitSet>(); 
    	for (int y=0; y<9; y++) {
        	for (int x=0; x<9; x++) {
        		Cell cell = getCell(x, y);
        		BitSet tmp = null;
                for (int value:args) {
                    if (cell.hasPotentialValue(value)) {
                    	tmp = (tmp==null) ? new BitSet() : tmp;
                    	tmp.set(value);
             		}
                }
                if (tmp!=null) potentials.put(cell, tmp);
        	}
    	}
    	return potentials;
	}

	/**
	 * This is used by the generator only
	 */
	public void setAll2Givens() {
    	for (int y=0; y<9; y++) {
        	for (int x=0; x<9; x++) {
        		Cell cell = getCell(x, y);
        		if (!cell.isEmpty()) cell.setIsGiven(true);
        	}
    	}
	}

	public void setDifficulty(double difficulty) {
		this.difficulty = difficulty;
	}

	public double getDifficulty() {
		return difficulty;
	}

}
